package com.atguigu.algorithm;

import java.util.Arrays;

public class QuickSort1 {
    public static void main(String[] args) {
        int[] a=new int[]{4, 81, 38, 23, 6, 33, 7, 40, 97, 46};
        System.out.println(Arrays.toString(a));
        quickSort(a,0,a.length-1);
        System.out.println(Arrays.toString(a));
    }
    public static void quickSort(int[] a,int L,int R){
        if(L>=R)return;
        swap(a,L+(int)(Math.random()*(R-L+1)),R);
        int[] p=partition(a,L,R);
        quickSort(a,L,p[0]-1);
        quickSort(a,p[1]+1,R);
    }
    public static void swap(int[] a,int i,int j){
        int tmp=a[i];
        a[i]=a[j];
        a[j]=tmp;
    }
    public static int[] partition(int[] a,int L,int R){
        int num=a[R];
        int left=L-1;
        int right=R;
        while(L<right){
            if(a[L]<num){
                swap(a,left+1,L);
                left++;
                L++;
            }else if(a[L]==num){
                L++;
            }else{
                swap(a,right-1,L);
                right--;
            }
        }
        swap(a,right,R);
        return new int[]{left+1,right};
    }
}
